﻿#include<iostream>
#include<set>
#include<map>
#include<string>

using namespace std;

//typedef pair<const Key, T> value_type;
//
//template <class T1, class T2>
//struct pair
//{
//	typedef T1 first_type;
//	typedef T2 second_type;
//
//	T1 first;
//	T2 second;
//	pair() : first(T1()), second(T2())
//	{}
//	pair(const T1& a, const T2& b) : first(a), second(b)
//	{}
//	
//};

//// empty (1) ⽆参默认构造
//explicit set(const key_compare& comp = key_compare(),
//	const allocator_type& alloc = allocator_type());
//
//// range (2) 迭代器区间构造
//template <class InputIterator>
//set(InputIterator first, InputIterator last,
//	const key_compare& comp = key_compare(),
//	const allocator_type & = allocator_type());
//
//// copy (3) 拷⻉构造
//set(const set& x);
//
//// initializer list (5) initializer 列表构造
//set(initializer_list<value_type> il,
//	const key_compare& comp = key_compare(),
//	const allocator_type& alloc = allocator_type());


//// 单个数据插⼊，如果已经存在则插⼊失败
//pair<iterator, bool> insert(const value_type& val);
//void insert(initializer_list<value_type> il);
//
//// 迭代器区间插⼊，已经在容器中存在的值不会插⼊
//template <class InputIterator>
//void insert(InputIterator first, InputIterator last);
//
////列表插入
//void insert(initializer_list<value_type> il);


//// 查找val，返回val所在的迭代器，没有找到返回end()
//iterator find(const value_type& val);
//// 查找val，返回val的个数
//size_type count(const value_type& val) const;


//// 删除一个迭代器位置的值
//iterator erase(const_iterator position);
//// 删除val，val不存在返回0，存在返回1
//size_type erase(const value_type& val);
//// 删除一段迭代器区间的值
//iterator erase(const_iterator first, const_iterator last);


//// 返回大于等于val位置的迭代器
//iterator lower_bound(const value_type & val) const;
//// 返回大于val位置的迭代器
//iterator upper_bound(const value_type& val) const;

//int main()
//{
	//set<int>s1;//构造一个某类型的空容器

	//string str("abcde");
	//set<char> s2(str.begin(), str.end());//使用迭代器构造某一段内容

	//set<char>s3(s2);//拷贝构造某类型set容器的复制品

	//set<string> strset = { "sort", "insert", "add" };//列表构造

	////插入单个元素,已经存在的值插入失败
	//set<int> s1;
	//s1.insert(8);
	//s1.insert(3);
	//s1.insert(1);

	////使用迭代器区间插入，已经存在的值插入失败
	//set<char> s2;
	//string str("bacde");
	//s2.insert(str.begin(), str.end());

	//// 插⼊⼀段initializer_list列表值，已经存在的值插入失败
	//set<int> s3;
	//s3.insert({ 2,8,3,9 });

	
	//set<int> s1;
	//s1.insert(8);
	//s1.insert(3);
	//s1.insert(1);

	//auto pos = s1.find(1);

	//if (pos != s1.end())
	//{
	//	cout << "存在" << endl;
	//} 
	//else
	//{
	//    cout << "不存在！" << endl;
	//}

	//cout << s1.count(1) << endl;//1
	//cout << s1.count(10) << endl;//0
//
//	return 0;
//}



//int main()
//{                                                                        
//	set<int> s = { 4,2,7,2,8,5,9 };
//	for (auto e : s)
//	{
//		cout << e << " ";
//	} 
//	
//	cout << endl;
//
//	// 删除最⼩值
//	s.erase(s.begin());//删除一个迭代器位置的值
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//
//	cout << endl;
//
//	// 直接删除x
//	int x;
//	cin >> x;
//	int num = s.erase(x);//删除val，不存在返回0，存在返回1
//	if (num == 0)
//	{
//		cout << x << "不存在！" << endl;
//	} 
//	
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	
//	cout << endl;
//	
//	s.erase(s.begin(), s. end());//删除一段迭代器区间的值
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	return 0;
//}

//int main()
//{
//	std::set<int> myset;
//	for (int i = 1; i < 10; i++)
//		myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
//
//	for (auto e : myset)
//	{
//		cout << e << " ";
//	}
//	
//	cout << endl;
//	// 实现查找到的[itlow,itup)包含[30, 60]区间
//	// 返回 >= 30
//	auto itlow = myset.lower_bound(30);//在这个示例里，返回30位置的迭代器，因为刚好有30存在
//	// 返回 > 60
//	auto itup = myset.upper_bound(60);//返回70 位置的迭代器
//	// 删除这段区间的值
//	myset.erase(itlow, itup);
//	for (auto e : myset)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//	return 0;
//}

//int main()
//{
//	set<int> s;
//	//插入元素（去重）
//	s.insert(4);
//	s.insert(2);
//	s.insert(7);
//	s.insert(2);
//	s.insert(8);
//	s.insert(5);
//	s.insert(9);
//	
//	for (auto e : s)
//	{
//		cout << e << " ";//2 4 5 7 8 9
//	}
//	cout << endl; 
//
//	s.erase(8);//删除单个元素
//	
//	set<int>::iterator pos = s.find(1); //查找值为1的元素，查找val，返回val所在的迭代器，没有找到返回end()
//	if (pos != s.end())
//	{
//		s.erase(pos);
//	}
//	//正向迭代器
//	set<int>::iterator it = s.begin();
//	while (it != s.end())
//	{
//		cout << *it << " ";//2 4 5 7 9
//		it++;
//	}
//	cout << endl; 
//
//	//容器中值为2的元素个数
//	cout << s.count(2) << endl; //1
//
//	//容器大小
//	cout << s.size() << endl; //5
//
//	//清空容器
//	s.clear();
//
//	//容器判空
//	cout << s.empty() << endl; //1
//
//	//交换两个容器的数据
//	set<int> tmp = { 8,3,5,1};
//	s.swap(tmp);
//
//	//反向迭代器
//	set<int>::reverse_iterator rit = s.rbegin();
//	while (rit != s.rend())
//	{
//		cout << *rit << " ";//8 5 3 1
//		rit++;
//	}
//	cout << endl; 
//	return 0;
//}

//int main()
//{
//	// 相比set不同的是，multiset是排序，但是不去重（支持值冗余）
//	multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };
//
//	auto it = s.begin();
//
//	while (it != s.end())
//	{
//		cout << *it << " ";
//		++it;
//	}
//    cout << endl;
//
//	// 相比set不同的是，x可能会存在多个，find查找中序的第⼀个
//	int x;
//	cin >> x;//4
//	auto pos = s.find(x);
//	while (pos != s.end() && *pos == x)
//	{
//		cout << *pos << " ";
//		++pos;
//	}
//	cout << endl;
//
//	// 相比set不同的是，count会返回x的实际个数
//	cout << s.count(x) << endl;
//
//	// 相⽐set不同的是，erase给值时会删除所有的x
//	s.erase(x);
//	for (auto e : s)
//	{
//		cout << e << " ";
//	} 
//	
//	cout << endl;
//	return 0;

//}

////////////////////////////////////////////////////////////////////////////////////////////////////////

//// empty (1) ⽆参默认构造
//explicit map(const key_compare& comp = key_compare(),
//	const allocator_type& alloc = allocator_type());
//// range (2) 迭代器区间构造
//template <class InputIterator>
//map(InputIterator first, InputIterator last,
//	const key_compare& comp = key_compare(),
//	const allocator_type & = allocator_type());
//// copy (3) 拷⻉构造
//map(const map& x);
//// initializer list (5) initializer 列表构造
//map(initializer_list<value_type> il, const key_compare& comp = key_compare(),
//	const allocator_type& alloc = allocator_type());

//int main()
//{
//	//构造一个key为int类型，value为string类型的空容器
//	map<int, string> m1;
//
//
//	map<int, string> m2 = { {1,"one"},{2,"two"},{3,"three"} };
//	map<int, string> m3(m2.begin(), m2.end());//使用迭代器构造m2容器某段区间的复制品
//
//	//拷贝构造
//	map<int, string> m4(m3);//拷贝构造key为int类型，value为string类型的m4容器的复制品
//
//	// initializer 列表构造
//	map<string, string> m5 = { {"left", "左边"}, {"right", "右边"},
//	{"insert", "插⼊"},{ "string", "字符串" } };
//	return 0;
//}

//Member types
//key_type->The first template parameter(Key)
//mapped_type->The second template parameter(T)
//value_type->pair<const key_type, mapped_type>
//// 单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败
//pair<iterator, bool> insert(const value_type& val);
//// 列表插⼊，已经在容器中存在的值不会插⼊
//void insert(initializer_list<value_type> il);
//// 迭代器区间插⼊，已经在容器中存在的值不会插⼊
//template <class InputIterator>
//void insert(InputIterator first, InputIterator last);



//int main()
//{
//
//	 //Member types
//     //key_type->The first template parameter(Key)
//     //mapped_type->The second template parameter(T)
//     //value_type->pair<const key_type, mapped_type>
//
//    // 单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败
//    //pair<iterator, bool> insert(const value_type& val);
//
//	////单个数据插入
//	//map<int, string> m1;
//	//m1.insert(pair<int, string>(1, "one"));
//	//m1.insert(pair<int, string>(2, "two"));
//	//m1.insert(pair<int, string>(3, "three"));
//
//	////一段initializer_list列表值插入
//	//map<int, string> m2 = { {1,"one"},{2,"two"},{3,"three"} };
//
//	////使用迭代器区间插入
//	//map<int, string> m3(m2.begin(), m2.end());
//
//	// insert插⼊pair对象的4种方式，对比之下，最后一种最方便
//	map<string, string> m1;
//	
//	pair<string, string> kv1("first", "第⼀个");
//	//1.
//	m1.insert(kv1);
//	//2.
//	m1.insert(pair<string, string>("second", "第⼆个"));
//	//3.
//	m1.insert(make_pair("sort", "排序"));
//	//4.
//	m1.insert({ "auto", "⾃动的" });
//
//
//
//	return 0;
//}

//// 查找k，返回k所在的迭代器，没有找到返回end()
//iterator find(const key_type& k);
//// 查找k，返回k的个数
//size_type count(const key_type& k) const;

//int main()
//{
//	map<int, string> m1 = { {1,"one"},{2,"two"},{3,"three"} };
//	auto it = m1.find(1);
//	if (it != m1.end())
//	{
//		cout << "存在" << endl;
//	}
//	else
//	{
//		cout << "不存在" << endl;
//	}
//
//	cout << m1.count(5) << endl;//0
//	cout << m1.count(2) << endl;//1
//	return 0;
//}

//// 删除⼀个迭代器位置的值
//iterator erase(const_iterator position);
//// 删除k，k存在返回0，存在返回1
//size_type erase(const key_type& k);
//// 删除⼀段迭代器区间的值
//iterator erase(const_iterator first, const_iterator last);


//int main()
//{
//
//	//map<int, string>m1 = { {1, "one"}, {2, "two"}, {3, "three"} ,{4,"four"},{5,"five"} };
//
//	//for (const auto& pair : m1)
//	//{
//	//	cout << pair.first << ": " << pair.second << endl;//first就是key，second就是value
//	//}
//
//	//m1.erase(m1.begin());//删除一个迭代器位置的数据
//
//	//for (const auto& pair : m1)
//	//{
//	//	cout << pair.first << ": " << pair.second << endl;
//	//}
//
//
//	//// 直接删除x
//	//int x;
//	//cin >> x;
//	//size_t num = m1.erase(x);//删除val，不存在返回0，存在返回1
//	//if (num == 0)
//	//{
//	//	cout << x << "不存在！" << endl;
//	//}
//
//	//for (const auto& pair : m1)
//	//{
//	//	cout << pair.first << ": " << pair.second << endl;
//	//}
//
//	//m1.erase(m1.begin(), m1.end());//删除一段迭代器区间的值
//
//	//for (const auto& pair : m1)
//	//{
//	//	cout << pair.first << ": " << pair.second << endl;
//	//}
//
//
//	return 0;
//}​



//int main()
//{
//	map<int, string>m1 = { {1, "one"}, {2, "two"}, {3, "three"} ,{4,"four"},{5,"five"} };
//
//	for (const auto& pair : m1)
//	{
//		cout << pair.first << ": " << pair.second << " ";//first就是key，second就是value
//	}
//	cout << endl;
//
//	m1.erase(m1.begin());//删除一个迭代器位置的数据
//
//	for (const auto& pair : m1)
//	{
//		cout << pair.first << ": " << pair.second <<" ";
//	}
//	cout << endl;
//
//	// 直接删除x
//	int x;
//	cin >> x;
//	size_t num = m1.erase(x);//删除val，不存在返回0，存在返回1
//	if (num == 0)
//	{
//		cout << x << "不存在！" << endl;
//	}
//
//	for (const auto& pair : m1)
//	{
//		cout << pair.first << ": " << pair.second << " ";
//	}
//	cout << endl;
//
//	m1.erase(m1.begin(), m1.end());//删除一段迭代器区间的值
//
//	for (const auto& pair : m1)
//	{
//		cout << pair.first << ": " << pair.second << " ";
//	}
//
//	cout << endl;
//	return 0;
//}

//// operator的内部实现
//mapped_type& operator[] (const key_type& k)
//{
//	// 1、如果k不在map中，insert会插入k和mapped_type默认值，同时[]返回结点中存储
//	//mapped_type值的引⽤，那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊ + 修改功能
//	
//	// 2、如果k在map中，insert会插入失败，但是insert返回pair对象的first是指向key结点的
//	//迭代器，返回值同时[]返回结点中存储mapped_type值的引⽤，所以[]具备了查找 + 修改的功能
//		pair<iterator, bool> ret = insert({ k, mapped_type() });
//	iterator it = ret.first;
//
//	return it->second;
//}

//int main()
//{
//	// 利⽤[]插⼊+修改功能，巧妙实现统计⽔果出现的次数
//	string arr[] = { "苹果", "西⽠", "苹果", "西⽠", "苹果", "苹果", "西⽠",
//	"苹果", "⾹蕉", "苹果", "⾹蕉" };
//	map<string, int> countMap;
//	for (const auto& str : arr)
//	{
//		// []先查找找果在不在map中
//		// 1、不在，说明水果第⼀次出现，则插入{⽔果, 0}，同时返回次数的引⽤，++⼀下就变成1次了
//		// 2、在，则返回水果对应的次数++
//		countMap[str]++;
//
//	}
//
//	for (const auto& e : countMap)
//	{
//		cout << e.first << ":" << e.second << endl;
//	}
//	cout << endl;
//	return 0;
//}

//int main()
//{
//	map<string, string> dict;
//	dict.insert(make_pair("sort", "排序"));
//
//	// key不存在->插⼊ {"insert", string()}
//	dict["insert"];
//
//	// 插⼊+修改
//	dict["left"] = "左边";
//
//	// 修改
//	dict["left"] = "左边、剩余";
//
//	// key存在->查找
//	cout << dict["left"] << endl;// "左边、剩余" ,因为operator[]的返回值是mapped_type(value)
//	return 0;
//}



//int main() 
//{
//	map<int, string> myMap = { {1, "one"}, {3, "three"}, {5, "five"}, {7, "seven"} };
//
//	for (auto e : myMap)
//	{
//		cout << e.first << " -> " << e.second << endl;
//	}
//
//	cout << endl;
//
//	//返回>=3
//	auto itlow = myMap.lower_bound(3);//在这个示例里，返回3位置的迭代器
//	//返回>5
//	auto itupper = myMap.upper_bound(5);//在这个示例里，返回7位置的迭代器
//	//删除这段区间的值
//	myMap.erase(itlow, itupper);//区间都是左闭右开
//
//	for (auto e : myMap)
//	{
//		cout << e.first << " -> " << e.second << endl;
//	}
//
//	cout << endl;
//
//	return 0;
//}

//int main()
//{	
//	map<int, string> m;
//	//去重
//	m.insert(make_pair(2, "two"));
//	m.insert(make_pair(1, "one"));
//	m.insert(make_pair(3, "three"));
//	m.insert(make_pair(3, "three"));
//	m.insert(make_pair(5, "five"));
//	m.insert(make_pair(8, "eight"));
//
//	for (auto e :m)
//	{
//		cout << e.first << " -> " << e.second << endl;
//	}
//		
//	cout << endl;
//
//	m.erase(1);//删除
//
//	//正向迭代器
//	map<int,string>::iterator it = m.begin();
//	while (it != m.end())
//	{
//		cout << it->first << " -> "<<it->second<< endl;
//		it++;
//	}
//	cout << endl;
//
//	map<int,string>::iterator pos = m.find(1); //查找值为1的元素，查找val，返回val所在的迭代器，没有找到返回end()
//	if (pos != m.end())
//	{
//		m.erase(pos);
//	}
//
//
//	//获取容器中元素的个数
//	cout << m.size() << endl; //4
//
//	//容器中key值为3的元素个数
//	cout << m.count(3) << endl; //1
//	//清空容器
//	m.clear();
//
//	//容器判空
//	cout << m.empty() << endl; //1
//	cout << endl;
//
//	//交换两个容器中的数据
//	map<int, string> tmp = { {1, "one"}, {2, "two"}, {3, "three"} ,{4,"four"},{5,"five"} };
//	m.swap(tmp);
//
//	//反向迭代器
//	map<int,string>::reverse_iterator rit = m.rbegin();
//	while (rit != m.rend())
//	{
//		cout << rit->first <<" -> " << rit->second << endl;
//		rit++;
//	}
//	cout << endl;
//
//	return 0;
//}


int main()
{
	// 相比map不同的是，multimap是排序，但是不去重（支持值冗余）
	multimap<int, string> m;
	m.insert(make_pair(2, "two"));
	m.insert(make_pair(1, "one"));
	m.insert(make_pair(3, "three"));
	m.insert(make_pair(3, "three"));
	m.insert(make_pair(5, "five"));
	m.insert(make_pair(8, "eight"));

	auto it = m.begin();

	while (it != m.end())
	{
		cout << it->first << " -> " << it->second << endl;
		++it;
	}
	cout << endl;

	// 相比map不同的是，x可能会存在多个，find查找中序的第⼀个
	int x;
	cin >> x;//3
	auto pos = m.find(x);
	while (pos != m.end() && pos->first== x)
	{
		cout << pos->first << " ";
		++pos;
	}
	cout << endl;

	// 相比map不同的是，count会返回x的实际个数
	cout << m.count(x) << endl;

	// 相⽐map不同的是，erase给值时会删除所有的x
	m.erase(x);
	for (auto e : m)
	{
		cout << e.first << " -> " << e.second << endl;
	}

	cout << endl;

	return 0;

}

